package com.test.daily.leetcode.y2022.m05.day0519.v01;

/**
 * @descriptions: Solution
 * @author: Tom
 * @date: 2022/5/19 上午 09:04
 * @version: 1.0
 */
public class Solution {
    public static void main(String[] args) {
        int start = 2;
        int rest = 11;
        int N = 6;
        int aim = 3;
        System.out.println(findNums(2, 11, 6, 3));
        int[][] dp = new int[N + 1][rest + 1];
        for (int i = 0; i < N + 1; i++) {
            for (int j = 0; j < rest + 1; j++) {
                dp[i][j] = -1;
            }
        }
        dp1(start, rest, N, aim, dp);
        System.out.println(dp[start][rest]);
        System.out.println(dp2(11, 6, 2, 3));
    }

    public static int findNums(int start, int rest, int N, int aim) {
        return process(start, rest, N, aim);
    }

    public static int process(int cur, int rest, int N, int aim) {
        if (rest == 0) {
            return cur == aim ? 1 : 0;
        }
        if (cur == 1) {
            return process(2, rest - 1, N, aim);
        }
        if (cur == N) {
            return process(N - 1, rest - 1, N, aim);
        }
        return process(cur + 1, rest - 1, N, aim) + process(cur - 1, rest - 1, N, aim);
    }

    public static int dp2(int K, int N, int start, int aim) {
        int[][] dp = new int[N + 1][K + 1];
        dp[aim][0] = 1;
        for (int rest = 1; rest < K + 1; rest++) {
            dp[1][rest] = dp[2][rest - 1];
            for (int cur = 2; cur < N; cur++) {
                dp[cur][rest] = dp[cur + 1][rest - 1] + dp[cur - 1][rest - 1];
            }
            dp[N][rest] = dp[N - 1][rest - 1];
        }
        return dp[start][K];
    }

    public static int dp1(int cur, int rest, int N, int aim, int[][] dp) {
        if (dp[cur][rest] != -1) {
            return dp[cur][rest];
        }
        int ans;
        if (rest == 0) {
            ans = cur == aim ? 1 : 0;
            dp[cur][rest] = ans;
        } else if (cur == 1) {
            ans = dp1(2, rest - 1, N, aim, dp);
        } else if (cur == N) {
            ans = dp1(N - 1, rest - 1, N, aim, dp);
        } else {
            ans = dp1(cur + 1, rest - 1, N, aim, dp) + dp1(cur - 1, rest - 1, N, aim, dp);
        }
        dp[cur][rest] = ans;
        return ans;
    }

}
